package linkedlist;

/**
 * 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
 * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
 */
public class no147 {
    public static void main(String[] args) {
        ListNode listNode = creat();
        insertionSortList(listNode);
    }
    public static ListNode creat(){
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        return listNode1;
    }
    public static ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode cur = head;
        ListNode prev = head.next;
        ListNode newPrev = head.next;
        ListNode newNode = new ListNode(-1);
        ListNode temp = newNode;
        newNode.next = head;
        while (prev != null){
            if(cur.val <= prev.val){
                prev = prev.next;
                cur = cur.next;
            }else{
                temp = newNode;
                while (temp != cur){
                    if(temp.next.val > prev.val){
                        newPrev = prev.next;
                        prev.next = temp.next;
                        temp.next = prev;
                        prev = newPrev;
                        cur.next = prev;
                        break;
                    }else{
                        temp = temp.next;
                    }
                }
            }
        }
        return newNode.next;
    }
}
